A distributed system is a network of interconnected computers or processors, each of which is called a "node." A distributed object is a resource or other entity that is available to a plurality of nodes in the distributed system. Examples of distributed objects include a resource such as a printer or lock request queue, a body of data such as a table in a relational database, and a thread, which contains executable instructions and program state. A distributed object, or each partition thereof, is located or "hosted" at a particular "host" node in the distributed system. For example, a distributed object that contains state is hosted at the node in the distributed system that provides memory to store the state information. Since a distributed object is available to other nodes in the distributed system, the distributed object, for example, can be created by one node in the distributed system to be hosted at another node, accessed by yet another node, and modified by still another node.
Typically, distributed objects are identified by their "name," which is a string of bits or other values such as ASCII characters. In order for a process executing at one node in a distributed system to use a distributed object, that process "resolves" the name of the distributed object to determine the location, i.e. the host node, of the distributed object. If the host node is the same node as that of the process, then the process can access the distributed object quickly and cheaply by interprocess communication techniques such as shared memory, named pipes, semaphores, and the like. On the other hand, if the distributed object is hosted at another node, then the process accesses the distributed object more slowly and expensively over a network connection, as by making a remote procedure call, establishing a TCP/IP link, passing a message and the like. It is thus desirable to host the distributed object at a node that has an affinity to the distributed object, for example, at the node that is executing most of the processes that are accessing the distributed object. Most accesses to the distributed object, when hosted at the node with an affinity thereto, are performed over the cheaper interprocess communications rather than the more expensive networking communications.
A distributed object is associated with both a name and a location. The process of converting a name of a distributed object into the location of the distributed object is called "name resolution" and depends on a particular "name clustering" strategy. One popular strategy, termed herein "syntactic clustering," is to couple the name of the host node to the name of distributed objects located at the host. A typical example is the "URL," the Uniform Resource Locator for the World Wide Web. A URL syntactically embeds the name of the host node in the name of the web object. For example, a URL for a home page on the World Wide Web of "http://www.foo.com/.about.bar/index.html" includes the substring "www.foo.com" for the name of the host machine. Syntactic name resolution accordingly involves parsing the name of the distributed object to determine the location of the distributed object.
A major disadvantage to syntactic clustering is apparent in reconfigurable distributed systems, especially in resilient or fault-tolerant networks, wherein a distributed object is able to survive the death of its host node, as by crashing or hanging. When a node is removed from such a distributed system, the distributed objects hosted at the node must be redistributed to other nodes in the distributed system. If the name of the host is syntactically encoded in the name of the distributed objects, the names of the redistributed objects are invalid after the redistribution, because they still identify the dead node. Therefore, processes accessing the relocated distributed objects can no longer locate them by the invalid names.
One conventional attempt to address the reconfiguration issue, termed "attribute clustering," is to provide an extra level of indirection in the naming scheme. Accordingly, the name of a distributed object does not directly encode the location of the distributed object, but is an attribute in a data structure such as a name table that stores the location of the distributed object. Name resolution in an attribute clustering scheme involves looking up the name in a table for an entry that includes a portion of the name and the corresponding location of the distributed object. When the distributed system is reconfigured, as by adding or removing a node, the name table must be updated to indicate the new host locations for the distributed objects.
Attribute clustering, however, entails several drawbacks. For example, this approach involves the creation of a very large data structure, which is time-consuming to search. Creation and deletion of distributed objects involves adding and removing entries in the name table, which is slow for large numbers of distributed objects and, hence, huge name tables. Furthermore, it is expensive to provide a copy of a huge name table at every site. One approach is to partition the name table and distribute portions of the table across the distributed system, in effect making the name table a distributed object, thereby increasing overhead in name resolution, because the relevant portions of the name table are often located often at another site.
In an "algorithmic clustering" approach, distributed objects are hosted at nodes based on the result of applying a global hash function to their respective names. Thus, the host node is independent of the name of the distributed object. When the distributed system is reconfigured, a new hash function is generated for the new configuration and the distributed objects of the distributed system are rehosted based upon the results of applying the new hash function to the names of the distributed objects. Since a distributed object is always located by hashing the name of the distributed object, the name of distributed object is still valid after reconfiguration. The major disadvantage of the algorithmic clustering approach is that a distributed object is usually not hosted at the node that has the most affinity to the distributed object. Thus, most of the accesses to the distributed object have to be performed by messages transmitted over a network channel. Consequently, the algorithmic clustering techniques involve high network communications overhead.
Therefore, conventional hosting methodologies are characterized by a Hobson's choice between efficiency and resiliency. Conventional syntactic clustering techniques are able to host a distributed object at the node having the most affinity for access efficiency but are incapable of efficiently redistributing the distributed object if the host node is removed. Conventional algorithmic clustering techniques are capable of redistributing distributed object after a reconfiguration of the distributed system but fail to locate distributed object at the nodes that have affinity thereto, respectively. Conventional attribute clustering techniques, which are capable of hosting the distributed object at a node having an affinity thereto and redistributing the hosted objects, are impractical because of high overhead in hosting maintenance and name resolution.